#ifndef __disjoint_sets_H__
#define __disjoint_sets_H__
/**
*  Disjoint Sets
*/
#include<map>
#include<vector>
#include<iostream>
template <class T=int>
class disjoint_sets {
    std::map<T,T> _parent;
    std::map<T,int> _rank;
    public:
   void addset(T x) {
        _parent[x]=x;
        _rank[x]=1;
    };
    T find(T x) {
        T y=_parent[x];
        while(y!=_parent[y]) {
            _parent[x]=_parent[y];
            y=_parent[y];
        }
        return y;
    }
    T merge(T &x,T &y) {
        x=find(x);y=find(y); //goto root
        if( _rank[x] >= _rank[y]) {
            _parent[y]=_parent[x];
            _rank[x]+=_rank[y];
            return _parent[x];
        } else {
            _parent[x]=_parent[y];
            _rank[y]+=_rank[x];
            return _parent[x];
        }
    };
   typedef std::map<T,std::vector<T> > set_map;
   set_map organize() {
         set_map m;
         for(typename std::map<T,T>::iterator it=_parent.begin();it!=_parent.end();it++) {
            T i=it->first;
            T p=find(i);
            m[p].push_back(i);
         }
         return set_map(m);
    }
};


#endif /* __disjoint_sets_H__ */

